//给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
//输出: 4
//解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。
// 
//
// 示例 2: 
//
// 
//
// 
//输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
//输出: 10
// 
//
// 
//
// 提示: 
//
// 
// m == heightMap.length 
// n == heightMap[i].length 
// 1 <= m, n <= 200 
// 0 <= heightMap[i][j] <= 2 * 10⁴ 
// 
//
// 
// Related Topics 广度优先搜索 数组 矩阵 堆（优先队列） 👍 373 👎 0

package leetcode.editor.cn;

import algorithms.question.class22.Code3_接雨水2;

import java.util.PriorityQueue;

/**
 * Java：接雨水 II
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P407_TrappingRainWaterIi {
    public static void main(String[] args) {
        Solution solution = new P407_TrappingRainWaterIi().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 最长挡板往里缩进
     * T: O(MN)
     * S: O(MN)
     */
    class Solution {
        public int trapRainWater(int[][] nums) {
            if (nums == null || nums.length < 3 || nums[0] == null || nums[0].length < 3) {
                return 0;
            }
            int ROW = nums.length;
            int COL = nums[0].length;
            // 小根堆
            PriorityQueue<Info> queue = new PriorityQueue<>((a, b) -> a.v - b.v);
            // 记录是否入堆
            boolean[][] access = new boolean[ROW][COL];
            // 最外围一圈入堆
            // 上下
            for (int i = 0; i < COL; i++) {
                queue.offer(new Info(nums[0][i], 0, i));
                queue.offer(new Info(nums[ROW - 1][i], ROW - 1, i));
                access[0][i] = true;
                access[ROW - 1][i] = true;
            }
            // 左右
            for (int i = 1; i < ROW - 1; i++) {
                queue.offer(new Info(nums[i][0], i, 0));
                queue.offer(new Info(nums[i][COL - 1], i, COL - 1));
                access[i][0] = true;
                access[i][COL - 1] = true;
            }
            int max = 0;
            int res = 0;
            while (!queue.isEmpty()) {
                Info cur = queue.poll(); // 弹出最小值
                max = Math.max(max, cur.v);
                int x = cur.x;
                int y = cur.y;
                // 上
                if (x - 1 >= 0 && !access[x - 1][y]) {
                    res += Math.max(0, max - nums[x - 1][y]);
                    queue.offer(new Info(nums[x - 1][y], x - 1, y));
                    access[x - 1][y] = true;
                }
                // 下
                if (x + 1 < ROW && !access[x + 1][y]) {
                    res += Math.max(0, max - nums[x + 1][y]);
                    queue.offer(new Info(nums[x + 1][y], x + 1, y));
                    access[x + 1][y] = true;
                }
                // 左
                if (y - 1 >= 0 && !access[x][y - 1]) {
                    res += Math.max(0, max - nums[x][y - 1]);
                    queue.offer(new Info(nums[x][y - 1], x, y - 1));
                    access[x][y - 1] = true;
                }
                // 右
                if (y + 1 < COL && !access[x][y + 1]) {
                    res += Math.max(0, max - nums[x][y + 1]);
                    queue.offer(new Info(nums[x][y + 1], x, y + 1));
                    access[x][y + 1] = true;
                }
            }
            return res;
        }

        private class Info {
            int v; // 值
            int x; // 横坐标
            int y; // 纵坐标

            public Info(int v, int x, int y) {
                this.v = v;
                this.x = x;
                this.y = y;
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}